package com.ting.test.algorithms.滑动窗口;

import java.util.LinkedList;

/**
 * Created by 雷霆 on 2020/11/6.
 * <p>
 * Description：
 * 假设一个固定大小为W的窗口，依次划过arr，
 * 返回每一次滑出状况的最大值
 * 例如，arr = [4,3,5,4,3,3,6,7], W = 3
 * 返回：[5,5,5,4,6,7]
 */
public class 固定窗口解法1 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int width = 3;
        int[] result = printLocalMax(arr, width);
        for (int res : result) {
            System.out.println(res);
        }
    }

    private static int[] printLocalMax(int[] arr, int width) {
        if (null == arr || arr.length < 1 || width < 0) {
            return null;
        }
        int length = arr.length;
        int index = 0, R = 0;
        int[] result = new int[length - width + 1];

        // 双端队列
        LinkedList<Integer> windows = new LinkedList<>();

        while (R < length) {
            while (!windows.isEmpty() && arr[R] >= arr[windows.peekLast()]) {
                windows.pollLast();
            }
            windows.addLast(R);

            //R - width == windows.peekFirst() 表示队头元素过期
            if (R - width == windows.peekFirst()) {
                windows.pollFirst();
            }
            //根据题意 只有窗口大小等于width时，才会记录最大值元素
            if (R >= width - 1) {
                result[index++] = arr[windows.peekFirst()];
            }
            R++;
        }
        return result;
    }


}
